題目

題目翻譯

給一個連結陣列，移除連結陣列從後面數來第n個節點

解題步驟

1. 問題描述：

   • 給定一個單鏈表，並且要求從該鏈表的倒數第 n 個節點處刪除該節點，最後返回新的鏈表的頭節點。

2. 思路分析：

   • 這個問題的關鍵是要找到從頭到尾的第 s - n 個節點（其中 s 是鏈表的總長度），這樣才能從倒數第 n 個節點的位置進行刪除。
   • 我們可以首先遍歷整個鏈表來計算出鏈表的總長度 s，然後再通過第二次遍歷找到第 s - n 個節點，並刪除它。
   • 當刪除的是頭節點時，特別處理，直接返回第二個節點作為新的頭節點。

3. 步驟分解：

   • 步驟1：計算鏈表的總長度 s。
   • 步驟2：找到從頭到第 s - n 個節點並刪除其後的節點。
   • 步驟3：若刪除的是頭節點，直接返回新的頭節點。
   • 步驟4：返回處理完的鏈表。

4. 邊界處理：

   • 如果刪除的是頭節點，需要特別處理，將 head 直接指向下一個節點。

code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 創建一個臨時指標指向頭節點，並初始化鏈表長度為 0
        ListNode* temp = head;
        int length = 0;
        
        // 遍歷整個鏈表，計算鏈表長度
        while (temp != nullptr) {
            length++;
            temp = temp->next;
        }
        
        // 計算要刪除的節點是從頭數的第幾個節點
        int position = length - n;
        temp = head;
        
        // 如果要刪除的是頭節點，直接返回頭節點的下一個節點
        if (position == 0) return head->next;
        
        // 找到從頭數第 position-1 個節點
        for (int i = 0; i < position - 1; ++i) {
            temp = temp->next;
        }
        
        // 刪除目標節點
        if (temp->next != nullptr) {
            temp->next = temp->next->next;
        }
        
        return head;
    }
};